\newcommand{\nweak}{\ensuremath{w}}
\newcommand{\weakperiod}{\ensuremath{\mathsf{\Gamma_\nweak}}}
\newcommand{\thweak}{\ensuremath{\tau_w}}
\newcommand{\numleak}{\ensuremath{\mathsf{leak}}}
\newcommand{\numanom}{\ensuremath{\mathtt{num\_anon}}}
\newcommand{\allvrfs}{\ensuremath{\mathtt{all\_vrfs}}}
\newcommand{\ub}{\ensuremath{\mathsf{ub}}}
\newcommand{\lb}{\ensuremath{\mathsf{lb}}}
\newcommand{\lbsumL}{\ensuremath{\underline{ \vrfwinninglist}^{\mathsf{sum}}}}
\newcommand{\ubL}{\ensuremath{\bar{\vrfwinninglist}}}
\newcommand{\eplen }{\ensuremath{R}}
\newcommand{\A }{\ensuremath{\mathcal{A}}}
\newcommand{\publicslots}{\ensuremath{\mathtt{public\_slots}}}
\newcommand{\phonestslots}{\ensuremath{\mathtt{p\_honest\_slots}}}
\newcommand{\honestslots}{\ensuremath{\mathtt{honest\_slots}}}
\newcommand{\malslots}{\ensuremath{\mathtt{mal\_slots}}}
\newcommand{\randweakslot}{\ensuremath{r\_weak\_slots}}
\newcommand{\publicvrfs}{\ensuremath{\mathtt{public\_vrfs}}}
\newcommand{\phonestvrfs}{\ensuremath{\mathtt{p\_honest\_vrfs}}}
\newcommand{\honestvrfs}{\ensuremath{\mathtt{honest\_vrfs}}}
\newcommand{\malvrfs}{\ensuremath{\mathtt{mal\_vrfs}}}
\newcommand{\malslotset}{\ensuremath{\mathcal{S}_m}}
\newcommand{\weakslotset}{\ensuremath{\mathcal{S}_w}}
\newcommand{\honestslotset}{\ensuremath{\mathcal{S}_h}}
\newcommand{\subslots}{\ensuremath{\mathbb{S}}}
\newcommand{\negl}{\ensuremath{\mathsf{negl}}}

\section{Analysis}




\subsection{Adversarial Model:} 
In our model, we assume that there exists $ n $ validators in synchronous network which means that any message arrive to other validators within $ T $ seconds where $ T $ is the slot duration. We consider two type of corruption in our model. We call the first corruption model \emph{strong corruption} and the second one \emph{weak corruption}. When a validator is strongly corrupted, it means that the current state (non-volatile memory) of the validator is shared with the adversary. We assume that every validator starts a new era with a freshly generated keys and erases the old keys. The adversary can strongly corrupt up to $ f = (1-\alpha)n $ validators in one era where $ \alpha \in (0,1] $ is the ratio of honest validators.  
When a validator is weakly corrupted, it means that the validator is not able to participate the protocol. The weak corruption basically silence the validator as if she does not exists during the corruption. The adversary can weakly corrupt up to $ \nweak $ validators at the same time at most  $ \weakperiod $ slots. A weakly corrupted validator is considered as malicious if she does not contribute the protocol as she is supposed to do because of the weakly corruption.  In other words, if the view of the protocol at the time that the validator is weakly corrupted is different than the view of the protocol without the corruption, then we assume this validator malicious and consider it as successful weakly corruption.  We denote honest validators set in one sortition and one block production phase by $ \mathcal{H} $ where $ |\mathcal{H}| = n_H = n-f - f_\nweak$ where $ f_\nweak $ is the number of malicious validators because of the weakly corruption.  Therefore, in our analysis below, we consider the security of Sassafras with $ f + f_{\nweak}$ malicious validators out of $ n $ validators. 

We analyze the number $ f_{\nweak} $ considering that the adversary can corrupt at most $ \nweak $ validators at the same time. For this, we analyze the best strategy for an adversary to maximize $ f_{\nweak} $ in Sassafras.


%Remark that the adversary needs to weakly corrupt constantly a validator to make this validator malicious because in this case the validator will not have any chance to submit her VRF values. 

This separation lets us analyse the security of Sassafras with more appropriate assumptions. Remark that a strongly corrupted validator behaves arbitrarily according to the adversarial will while weakly corrupted validator just stops running on time within $ \weakperiod $ slots. For example, the adversary can never make a weakly corrupted validator to construct on top of non-best chain. Therefore, weakly corrupted validators do not help  the adversary to construct a chain to break common prefix property or existential chain quality.  However, they help the adversary without consent to reduce the chain growth because they stop producing blocks or they produce blocks much later than expected.




The sub phases that is executed to decide block producers of epoch $ e $ takes $ l $ epochs.	
In these $ l $ epochs, the period that a validator generates and sends VRFs to repeater takes $ \Gamma_{\mathsf{vrf}} $ slots, that a repeater publishes all VRFs takes $ \Gamma_{\mathsf{rep}} $ slots and that the validator publishes her unpublished VRFs takes $ \Gamma_{\mathsf{last}} $ slots. We assume that $ \Gamma_{\mathsf{vrf}}, \Gamma_{\mathsf{rep}}, \Gamma_{\mathsf{last}}> \weakperiod $. It implies thatthe weak corruptions during sub phases will never be successful because after a validator is weakly corrupted during $\weakperiod $ slots, she will still have time to complete the sub-phase. So the view of the protocol does not change\footnote{We can also consider the adversary where $ \weakperiod > \Gamma_{\mathsf{vrf}}, \Gamma_{\mathsf{rep}}, \Gamma_{\mathsf{last}} $ but it requires more complicated analysis. So, it is left as a future work.} in all sub phases. 





%\paragraph{Honest Slot:} We call a slot associated with a VRF value $ \omega_{V,e,i} $ is an honest slot  if $ V $ is an honest validator and $ \mathcal{V}[H(\omega_{V,e,i}||``WHO'')] $ is not a corrupted validator. Therefore, the probability of having an honest slot is $ p_{\mathsf{hslot}} = \alpha^2 $.  


\paragraph{Public Slot:} We call a slot associated with a VRF value $ \omega_{V,e,i} $ is a weak slot  if $ V $ is an honest validator and $ \mathcal{V}[H(\omega_{V,e,i}||``WHO'')] $ is not a corrupted validator. Therefore, the probability of having a weak slot is $ p_{\mathsf{pSlot}} = \alpha (1-\alpha) $.  

\paragraph{Malicious Slot:}  We call a slot associated with a VRF value $ \omega_{V,e,i} $ is a malicious slot  if $ V $ is a strongly corrupted validator. Therefore, the probability of having a malicious slot is $ p_{\mathsf{mSlot}} =  (1-\alpha) $.  



\paragraph{Rand-Weak Slot:} We call a slot associated with a VRF value $ \omega_{V,e,i} $ is a random weak slot  if $ V $ is an honest validator and $ \mathcal{V}[H(\omega_{V,e,i}||``WHO'')] $ is not a corrupted validator and the adversary weakly corrupts $ V $ in the slot with the VRF value $ \omega_{V,e,i} $.  Below, we find the probability of having rand-weak slot $ p_{rSlot} $.

\begin{lemma}\label{lem:pr}
	The probability that a slot is a rand-weak is less than $$(1 - \exp(-\frac{\mu_{\mathsf{hvrf}}\delta_{\mathsf{hvrf}}}{2}))\frac{\nweak \vrfaattemptsbound }{\mu_{\mathsf{hvrf}} (1- \delta_{\mathsf{hvrf}}) - (\eplen  -1)} $$ where $ 0 < \delta_{\mathsf{hvrf}} < 1 $, $ \mu_{\mathsf{hvrf}} = (n-f)c\alpha\vrfaattemptsbound $ and  $ \eplen  $ is the epoch length.
\end{lemma}

\begin{proof}
	Consider a slot $ sl $ in an epoch $ e $ with the VRF input $ (r_e||i) $. Since $ (r_e||i) $ of the VRF output of $ sl $ is public, the adversary can eliminate validators for this slot $ sl $ to weakly corrupt who have already produced a block on a slot with the VRF input-index $ i $ and public validators who will produce with VRF input-index $ i $ in next slots. Let's call such validators \emph{inactive} for slot $ sl $ and assume that their number is $ n_i $. After eliminating the inactive validators, the adversary can compute the probability that an active  and honest validator $ V $ is selected in slot $ sl $ based on the number of blocks that she produced so far $ (\ell_V) $ and. So, this probability is where $ \mathcal{H}_a$ is the set of active validators:
	
	%$$p_{V,s} = \frac{|\vrfwinninglist_V|- \ell_V}{\sum_{V' \in \mathcal{H}_a}|\vrfwinninglist_{V'}| -\ell_{V'}-\numleak} \leq \frac{\vrfaattemptsbound - \ell_V}{\numanom - (s-1)}$$
	
	\begin{equation}\label{eq:prVs}
	p_{V,sl} = \frac{|\vrfwinninglist_V|- \ell_V}{\honestvrfs - \sum_{V' \in \mathcal{H}_a}\ell_{V'}}\leq \frac{\vrfaattemptsbound - \ell_V}{\honestvrfs - (R-1)}
	\end{equation}
	
	
	where $ \honestvrfs $ is the number of honest validators' VRF outputs which are anonymous to the adversary.
	In this case the best strategy for the adversary to increase her chance to  weakly corrupt the right validator  is sorting the list $ \{p_{V,sl}\}_{V \in \mathsf{Active}} $ in ascending order, and weakly corrupting the first $ w $ of the validators in the sorted $ \{p_{V,sl}\}_{V \in \mathsf{Active}} $. Therefore, the probability that being a rand-weak slot is less than $  \frac{\nweak\vrfaattemptsbound }{\honestvrfs - (R-1)}  $.
	
	Now let's lower bound $ \honestvrfs $ to upper bound $ p_{\mathsf{rweak}} $.	For this, we define a random variable $ R_{V,e,i} $ which is 1 if $ V $ is an honest validator, $ U = \vals[H(\omega'_{V,e,i} \| "WHO") \mod |\vals|]  $ corresponds to  \emph{an honest validator}, $ \omega'_{V,e,i} < c $. Otherwise, it is 0.  In this case, $ \pr[R_{V,e,i} = 1] = \alpha c$ and
	the expected number of $ R_{V,e,i}  = 1$ is  $ \mu_{\mathsf{hvrf}} = (n-f) \vrfaattemptsbound \alpha c $. We can bound the probability of having $ \honestvrfs $ close to the expected value with  the Chernoff bound as follows for all $ 0 <\delta_{\mathsf{hvrf}} < 1 	 $:
	
	\begin{equation}\label{eq:beforeepcoh}
	\pr[ \honestvrfs = \sum_{\substack{ \forall V \in \mathcal{H} \\0\leq i < \vrfaattemptsbound}} R_{V,e,i} \leq \mu_{\mathsf{hvrf}} (1 - \delta_{\mathsf{hvrf}})] < \exp(-\frac{\mu_{\mathsf{hvrf}}\delta_{\mathsf{hvrf}}^2}{2}) \nonumber
	\end{equation}
	
	Hence, we can upper bound the probability of having a rand-weak slot with
	$$(1 - \exp(-\frac{\mu_{\mathsf{hvrf}}\delta_{\mathsf{hvrf}}}{2}))\frac{\nweak \vrfaattemptsbound }{\mu_{\mathsf{hvrf}} (1- \delta_{\mathsf{hvrf}}) - (\eplen  -1)} $$
\end{proof}

\paragraph{Honest Slot:} We call a slot associated with a VRF value $ \omega_{V,e,i} $ is an honest slot  if it is not neither a malicious slot, nor public slot or rand-weak slot. Therefore, the probability of having an honest slot is $ p_{\mathsf{hSlot}} = 1- p_{\mathsf{mSlot}} - p_{\mathsf{pSlot}} - p_{\mathsf{rSlot}}  $.  

\subsection{Security Definitions}


\begin{definition}[Honest Chain Growth (HCG) \cite{genesi}]\label{def:hcg}
	The HCG property with parameters $ s_{hcg} \in \mathbb{N} $ ensures that the sub-chain $  \mathbf{B}[sl_u + sl_v] $ of a blockchain $ \mathbf{B} $ owned by an honest validator has the length at least $ s_{hcg}\tau_{hcg} $ where $ sl_u $ and $ sl_v \geq sl_u + s_{hcg} $ 	are assigned to honest validators.
\end{definition}


\begin{definition}[Chain Growth (CG) Property \cite{backbone}] \label{def:cg}
	The CG property with parameters $ s \in \mathbb{N} $ ensures that the sub-chain $  \mathbf{B}[sl_u + sl_v] $ of a blockchain $ \mathbf{B} $ owned by an honest validator has the length at least $ s_{hcg}\tau_{hcg} $ with $ sl_u $ and $ sl_v \geq sl_u + s_{hcg} $.
\end{definition}


\begin{definition}[Existential Chain Quality (ECQ) Property \cite{backbone}]\label{def:cq}
	The CQ property with parameter $ k \in \mathbb{N} $ ensures that the ratio of honest blocks in any $ k $ length portion of a blockchain owned by an honest party is at least $ \frac{1}{k}$.
\end{definition} 




\begin{definition}[Common Prefix (CP) Property \cite{backbone}] \label{def:cp}
	Common prefix with parameters $k \in \mathbb{N}$ ensures that any chains $\mathbf{B}_1, \mathbf{B}_2$ possessed by two honest validators at the onset of the slots $sl_1 < sl_2$ are such satisfies $\mathbf{B}_1^{\ulcorner k} \leq \mathbf{B}_2$ where  $\mathbf{B}_1^{\ulcorner k}$ denotes the chain obtained by removing the last $k$ blocks from $\mathbf{B}_1$, and $\leq$ denotes the prefix relation.
\end{definition}

\subsection{Security Proof}

\begin{lemma}[ECQ]\label{lem:ecq}
	If $ p_{\mathsf{mSlot}} < p_{\mathsf{hSlot}} $, the adversary breaks the existential chain quality with the parameter $ \malslots $ except with probability $ 1- \exp(-\Omega(k)) $.
\end{lemma}

\begin{proof}
	
	Let's consider consecutive $ k_{ecq} $ blocks $ B_1, B_2, ..., B_{k_{ecq}} $ of a chain $ \mathbf{B} $ owned by an honest validator  and assume that all of them generated by a malicious validator. Imagine that the first honest block before $ B_1 $ is $ B_{h_1}  \in \mathbf{B}$  and the first honest block after $ B_{k_{ecq}} $ is $ B_{h_2}  \in \mathbf{B}$. Remark that $ B_{h_1} $ exists because it is the genesis block in the worst case. Also, $ B_{h_2} $ exists because it is owned by an honest validators so in the worst case it is the last block of $ \mathbf{B} $. We know that the difference between the length of the chain whose last block is generated by the honest validator and the length of the chain whose last block is generated by the next honest validator is at least one because honest validators always build on top of the longest chain. Therefore, the length of the other chains that the honest validators build will be at least the number of honest slots $ (h) $ between the slot of $ B_{h_1} $ and $ B_{h_2} $. Since $ \mathbf{B} $ is the honest validator's best chain, it is longer than other chains meaning that $ k_{ecq} \geq h $.  Since $ p_{\mathsf{mSlot}} < p_{\mathsf{hSlot}} $ the probability that there are less than $ k_{ecq} $ honest slots given that there are $ k_{ecq} $ malicious slots is  falls exponentially with $ k_{ecq} $.
\end{proof}


\begin{lemma}[CP]\label{lem:cp}
	Assuming that probability that having  $ p_{\mathsf{hSlot}} >\frac{1}{2}$, Sassafras satisfies the common prefix property  with the parameter $ k $ except with the probability  $ \exp(-\Theta(k)) $. 
\end{lemma}

Thanks to the result of  Kiayias et al. \cite{consistency}, that if probability that having an honest slot is greater than the probability of having malicious slot and weak slot, chain prefix property is guaranteed with the error bound $ \exp(-\Theta(k)) $.

If a weakly corrupted validator informs everyone after the corruptions, then the chain that includes his block could be ignored by other validators. Thus, weakly corrupted validators do not help the adversary to break the common prefix property. If we had such mechanism in Sassafras, then having $ p_{\mathsf{hSlot}}  > p_{\mathsf{mSlot}} $ would be enough to achieve CP. 


\begin{lemma}[HCG]\label{lem:hcg}
	Sassafras satisfies the honest chain growth property with $ \tau_{hcg} = p_{\mathsf{hSlot}}(1-\delta_{\mathsf{hSlot}})  $ in $ s_{hcg} $ slots except with the probability $ \exp(-\frac{s_{hcg}p_{\mathsf{hSlot}}\delta_{\mathsf{hSlot}}^2}{2}) $ where $ 0< \delta_{\mathsf{hSlot}} < 1 $.
\end{lemma}

\begin{proof}
	Consider a chain $ \mathbf{B} $ owned by an honest validator at slot $ sl $. Let $ sl_u $ and $ sl_v $ be two previous slots where $ \mathbf{B}[sl_u] $ and $ \mathbf{B}[sl_v] $ are generated by honest validators and $ sl_u + s_{hcg} \leq sl_v $. As discussed in  Lemma \ref{lem:ecq}, the chain grows between $ \mathbf{B}[sl_u] $ and $ \mathbf{B}[sl_v] $ at least the number of honest slots. Therefore, let's upper bound the honest slots with the Chernoff bound for all $ 0<\delta_{\mathsf{hSlot}}<1 $.
	
	\begin{equation}
	\pr[\honestslots = \sum_{sl_u}^{sl_v}S_i \leq s_{hcg} p_{\mathsf{hSlot}}(1-\delta_{\mathsf{hSlot}})] < \exp(-\frac{s_{hcg}p_{\mathsf{hSlot}}\delta_{\mathsf{hSlot}}^2}{2})
	\end{equation}
	
	
\end{proof}


\begin{lemma}[CG]\label{lem:cg}
	Assuming that ECQ property is satisfied with the parameter $ k_{ecq}  $, Sassafras satisfies CG property with the parameter $ s = 2s_{ecq} + s_{hcg} $ and $ \tau =  \tau_{hcg} \frac{s_hcg}{2 s_{ecq} + s_{hcg}}   $ where $ s_{ecq} \tau  \leq k_{ecq} \leq s_{ecq} $ except with the probability $ \exp(-\frac{s_{hcg}p_{\mathsf{hSlot}}\delta_{\mathsf{hSlot}}^2}{2}) +  \exp(-\Omega(k)) $ .
\end{lemma}

\begin{proof}
	Consider the sub-chain $ B[sl_i,sl_i+s_{ecq}] $ spanned between slots $ sl_i $ and $ sl_i + s_{ecq} $  which is the sub-chain of a best chain in slot $ sl_i +  2s_{ecq} + s  $. Thanks to the ECQ property $ B[sl_i,sl_i+s_{ecq}] $ contains at least one block $ B_1 $ generated in an honest slot because  $ s_{ecq} \tau\leq k_{ecq} $.   Now, consider another sub-chain $ B[sl_j -s_{ecq} :sl_j] $ of the best chain spanned between slots $ sl_j - s $ and $ sl_j $ where $ sl_j $  is the last slot of $ e $. Similarly, $ B[sl_j -s_{ecq} :sl_j] $ contains at least one block $ B_2 $ generated on an honest slot. Lastly, we consider another sub-chain between blocks $ B_1 $ and $ B_2 $.  Thanks to honest chain growth, the length of the the sub-chain between $ B_1 $ and $ B_2 $ is at least equal to $ s p_{\mathsf{hSlot}(1-\delta_{\mathsf{hSlot}}))} $. So, the chain grows in $ 2s_{ecq} + s_{hcg} $ slots at least $ s_{hcg}\tau_{hcg} $ which implies that $ \tau = \tau_{hcg} \frac{s_hcg}{2 s_{ecq} + s_{hcg}} $ \cite{genesis} and $ s = 2s_{ecq} + s_{hcg} $. 
\end{proof}



\begin{theorem}\label{th:sec}
	Assuming that  $ p_{\mathsf{hSlot}} >\frac{1}{2}$ and given that  $k_{ecq}$ is the ECQ parameter, $k > 2k_{ecq}$ is the CP parameter, $s_{hcg} = k/\tau_{hcg}$, $s_{ecq} = k_{ecq}/\tau$, the epoch length is $\eplen  = 2s_{ecq} + s_{hcg}$, Sassafras is secure.
\end{theorem}

\emph{Proof Sketch:}
The overall result says that $\tau = \tau_{hcg}\frac{s_{hcg}}{2s_{ecq}+s_{hcg}} = \frac{k}{s_{hcg}}\frac{s_{hcg}}{2s_{ecq}+s_{hcg}} = \frac{k}{\eplen }$. The best chain at the end of an epoch grows at least $k$ blocks in one epoch thanks to the chain growth.

Since $k > 2k_{ecq}$, the last $k_{ecq}$ block of includes at least one honest block. Therefore, the randomness includes one honest randomness and the adversary can have at most $s_{ecq}$ slots to change the randomness. This grinding effect can be upper-bounded by $s_{ecq}(1-\alpha)nq$ where $q$ is the hashing power \cite{ouroboros}. The randomness generated by an epoch is finalized at latest one epoch later thanks to the common prefix property. Similarly, the session key update which is going to be used in three epochs later is finalized one epoch later before a randomness of the epoch where the new key are going to be used starts to leak.

